This invention relates generally to digital circuitry, and more particularly to digital circuitry adapted to reverse the order of the bits in a selected portion of a digital word.
As is known in the art, it is sometimes necessary to reverse the order of the bits or a portion of the bits in a digital word. For example, many Fast Fourier Transform (FFT) processors efficiently perform data manipulations by storing numerous pieces of data into memory at one set of addresses, but reversing the order of bits in the words containing those addresses before retrieving the data from the memory. The data is retrieved from memory in the order in which it is used, thus avoiding the need for any processing dedicated to sorting the data.
The key to the efficiency of processors using bit reversing is that the bit reversing takes less processing than the data sorting which would otherwise be required. One such bit reversing apparatus is described in U.S. Pat. No. 4,181,976, inventors Michael J. Collins and Michael T. S. Ching, issued Jan. 1, 1980 and assigned to the same assignee as the present invention. Although that patent describes apparatus which can reverse the order of the bits in a portion of the word located at one end of the word, it does not accommodate the more general case of reversing the bits in a portion of the word located in the middle of the word. Moreover, significant advantages can be obtained by using low complexity techniques to reverse the bits in a word such that the bit reversing hardware requires a small area on an integrated circuit.